package main

import "math"

// dfs解法超时~~
func minPathSum(grid [][]int) int {
	n, m := len(grid)-1, len(grid[0])-1
	min := math.MaxInt32
	// 定义行为方向
	dir := [][]int{{0, 1}, {1, 0}}
	// 定义递归函数
	var dfs func(i, j, total int)
	// 定义去重数组
	used := make([][]bool, n+1)
	for i := 0; i < n+1; i++ {
		used[i] = make([]bool, m+1)
	}
	used[0][0] = true
	dfs = func(i, j, total int) {
		if i == n && m == j {
			if min > total {
				min = total
			}
			return
		}
		for _, ac := range dir {
			x := i + ac[0]
			y := j + ac[1]
			// 判断是否越界 是否重复使用
			if x > n || x < 0 || y > m || y < 0 || used[x][y] {
				continue
			}
			used[x][y] = true
			dfs(x, y, total+grid[x][y])
			used[x][y] = false
		}
	}

	dfs(0, 0, grid[0][0])
	return min
}

// 这题官方解法是使用 动态规划，下面是官方代码
func minPathSum(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}
	rows, columns := len(grid), len(grid[0])
	dp := make([][]int, rows)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, columns)
	}
	dp[0][0] = grid[0][0]
	for i := 1; i < rows; i++ {
		dp[i][0] = dp[i-1][0] + grid[i][0]
	}
	for j := 1; j < columns; j++ {
		dp[0][j] = dp[0][j-1] + grid[0][j]
	}
	for i := 1; i < rows; i++ {
		for j := 1; j < columns; j++ {
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
		}
	}
	return dp[rows-1][columns-1]
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}
